package j2024.j202410;

import java.util.Scanner;

public class j1030 {
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] hash = new int[128];
        int ret = 0;
        char chret = 0;
        while (in.hasNext()){
            String str = in.next();
            for (int i = 0; i < str.length(); i++) {
                hash[str.charAt(i)-'a']++;
                if(hash[str.charAt(i)-'a'] > ret){
                    ret = hash[str.charAt(i)-'a'];
                    chret = str.charAt(i);
                }
            }
        }
        System.out.println(chret);
    }

    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] dp = new int[n+1];
        for (int i = 0; i <= n; i++) {
            dp[i] = 0x3f3f3f3f;
        }
        dp[0] = 0;
        for (int i = 1; i*i <= n; i++) {
            for (int j = i*i; j <= n; j++) {
                dp[j] = Math.min(dp[j],dp[j-i*i]+1);
            }
        }
        System.out.println(dp[n]);
    }

    /**
     * 86. 分隔链表
     * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
     *
     * 你应当 保留 两个分区中每个节点的初始相对位置。
     * @param head
     * @param x
     * @return
     */
    public ListNode partition(ListNode head, int x) {
        ListNode small = new ListNode(-1);
        ListNode large = new ListNode(-1);
        ListNode tmp = head;
        ListNode ret = small;
        ListNode lar = large;
        while(tmp!=null){
            if(tmp.val < x){
                small.next = tmp;
                small = small.next;
            }else {
                large.next = tmp;
                large = large.next;
            }
            tmp = tmp.next;
        }
        large.next = null;
        small.next = lar.next;
        return ret.next;
    }
}
